Early digital computer systems were single user machines. That is, a single program or job took control of the entire computer, monopolizing all of its resources such as the CPU, memory, secondary disk storage and peripherals such as terminals and printers. It was quickly realized that this was a very inefficient use of costly computer hardware. One of the major reasons that computer software called operating systems were developed was to allow more than one user to use a computer system at a time.
It is the operating system's task to maximize the amount of work that a set of users can perform on a given computer system. The set of user jobs submitted to a computer system for processing is called the workload.
One of the major functions performed by a computer operating system is job scheduling or managing the workload. Job scheduling involves giving user jobs access to the computer system resources, especially the central processing unit (CPU). All jobs are not treated equally in most operating systems. Just as there are different categories of customers at a bank with differing importance and priorities, there are different classes of users on a computer system.
Over the years many different resource scheduling algorithms have been developed. The simplest job scheduling algorithm is first come first served. This is similar to a bank office with a single active teller. Each customer comes in the door and gets in line. The customer is served only after all of the customers ahead in line are served. A disadvantage of this algorithm is that if the first customer has a very long transaction, all of the other customers must wait.
Another job scheduling algorithm is shortest job first. In this approach (continuing the bank analogy), each customer is asked how many transactions he needs to make, and the one with the least number of transactions is served first. On average, this algorithm gives the best performance. Of course, it is hard to tell in advance how long it will actually take to serve the customer. He may have only one transaction, but it may be extremely complicated and take 15 minutes. Another customer may have two transactions which will only take one minute each. This difficulty in knowing ahead of time how long the customer is going to take has prevented the shortest job first algorithm from being used in computers. Another problem is that a customer with a large number of transactions may never get served! If new customers keep coming in the bank, they will get served ahead of him. This is called starvation. For this reason, it is desirable to introduce the concept of "fairness" in a job scheduler. A good scheduling algorithm is both efficient and fair.
To overcome these problems, priorities can be assigned to various classes of customers. Usually within a class, customers would be served in first come first served order. Suppose for example that there are three classes of customers, private, small business, and large business, having priorities of 1, 2, and 3 respectively, where higher is better. If one of each walks in the door at the same time, they will be served in this order: large business, small business, and private. If when the small business customer is being served, another small business customer comes in the door, he will cut in line before the private customer. This is called priority scheduling.
Even with the addition of priorities, job scheduling is still not as good as it could be. Another innovation has been to monitor the behavior of the job in the system to determine where the job should stand in line. Thus a customer would initially get in line at the appropriate place based on his priority. But if a customer being served was taking an unusually long time, he would have to give up his spot and move back to a position in the line. In this way the customers would each get served for at least some period of time during each time through the line. When all of the customers have the same priority, this is called round robin scheduling. In cases where customers have different priorities, a hierarchy of lines is developed, and customers who use too much time will get bumped to lower and lower priority levels. These is called multilevel feedback queues.
In 1988, IBM researchers Franaszek and Nelson explored the use of a delay-cost scheduler. This scheduling algorithm works on the idea that for each customer in the store there is an associated cost that must be paid if the customer is delayed. At any time, the scheduler picks the customer with the highest delay cost to serve next. In a significant departure from the previously described algorithms, the delay cost scheduler does not use static (fixed) priorities. You could think of the delay cost values as the dynamic (changing) priority of each customer. The priority changes as a function of the customer's time in the system, and the longer the customer stays in the system the higher his delay cost (priority) becomes. Each distinct class of customers would have its own associated delay cost curve or function.
The delay cost scheduler has the potential for providing efficient service to a set of job classes, yielding good average response times, and avoiding job starvation. However, in order to take advantage of the delay cost job scheduler, the appropriate delay cost (priority) functions must be determined. Unfortunately, this is not a straight-forward or easy process. Initial efforts have used linear (straight-line) delay-cost curves of arbitrary slope. Without a systematic and reliable method for constructing an appropriate delay cost function, the full potential of a delay cost scheduler can not be realized.